package answer

/**
 * @Description: 通过快慢指针来实现，先走到中点，然后反转后半部分，然后再一块遍历
 */
func JudgeByTwoPoint(head *ListNode) bool {
	fast, low := head, head
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		low = low.Next
	}
	//如果fast不为空，说明链表的长度是奇数个
	if fast != nil {
		low = low.Next
	}
	low = reverse(low)
	fast = head
	for low != nil {
		if low.Val != fast.Val {
			return false
		}
		low = low.Next
		fast = fast.Next
	}
	return true
}

/**
 * @Description: 反转链表 已经将链表结构改造了
 */
func reverse(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	node := reverse(head.Next)
	head.Next.Next = head
	head.Next = nil
	return node
}
